// Package _05__从前序与中序遍历序列构造二叉树
// Date        : 2022/4/2 18:57
// Version     : 1.0.0
// Author      : 代码小学生王木木
// Email       : 18574945291@163.com
// Description :
package main

import "fmt"

// TreeNode
// @Description:
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// buildTree
// @Description:
// @param preorder
// @param inorder
// @return *TreeNode
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 || len(preorder) != len(inorder) {
		return nil
	}
	// 1. 确定根节点的值
	head := &TreeNode{
		preorder[0], nil, nil,
	}
	// 在中序遍历中 获取根节点的位置
	rootIndex := -1
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == preorder[0] {
			rootIndex = i
			break
		}
	}
	t1 := preorder[1 : len(inorder[:rootIndex])+1]
	t2 := inorder[:rootIndex]
	fmt.Println(t1, t2)
	head.Left = buildTree(t1, t2) //
	t3 := preorder[len(inorder[:rootIndex])+1:]
	t4 := preorder[len(inorder[:rootIndex])+1:]
	fmt.Println(t3, t4)
	head.Right = buildTree(t3, t4)
	return head
}

func main() {
	preorder := []int{3, 9, 20, 15, 7}
	inorder := []int{9, 3, 15, 20, 7}
	buildTree(preorder, inorder)
}
